#include<bits/stdc++.h>
using namespace std;
#define int long long
int q,x,y,X,Y,a,b,ans;
signed main()
{
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout); 
	scanf("%lld",&q);
	for(int i = 1;i <= q;i++)
	{
		scanf("%lld%lld",&x,&y); 
		a = b = 1,X = x,Y = y,ans = x*y/__gcd(x,y);
		for(int i = 2;i <= max(sqrt(x),sqrt(y));i++)
		{
			if(x % i == 0 && a == 1) a = i;
			if(y % i == 0 && b == 1) b = i;
			if(X % i == 0 && Y % i == 0) ans = min(ans,x+y);
			while(Y % i == 0) Y /= i;
			while(X % i == 0) X /= i;
		}
		if(X != 1 && a == 1) a = X;
		if(Y != 1 && b == 1) b = Y;
		if(X != 1 && X == Y) ans = min(ans,x+y);
		if(a != b) 
		{
			if(a == 2) ans = min(ans,x-(x==a)*x+b*2/__gcd(2ll,b)+y-(y==b)*y);
			else if(b == 2) ans = min(ans,x-(x==a)*x+a*2/__gcd(2ll,a)+y*2/__gcd(2ll,y));
			else ans = min(ans,x-(x==a)*x+min(a*2/__gcd(2ll,a)+b*2/__gcd(2ll,b),a*b/__gcd(a,b))+y-(y==b)*y);
		}
		printf("%lld\n",ans); 
	}
	return 0;
}
/*
1
3 25
*/
